package com.leet.code.lcof;

public class Code63 {
    public static void main(String[] args) {
//        int[] prices = {7,1,5,3,6,4};
        int[] prices = {3, 3, 5, 0, 0, 3, 1, 4};
        System.out.println(new Code63().maxProfit(prices));

    }

    public int maxProfit(int[] prices) {
        int min = 0, max, x = 0, xt, i = 1;

        while (i < prices.length && prices[i] <= prices[min]) {
            min = i;
            i++;
        }
        if (prices.length == i) {
            return 0;
        }
        max = i;

        while (i < prices.length) {
            if (prices[i] < prices[max] && prices[i] >= prices[min]) {
                i++;
            } else if (prices[i] >= prices[max]) {
                while (i < prices.length && prices[i] >= prices[max]) {
                    max = i;
                    i++;
                }
                xt = prices[max] - prices[min];
                if (xt > x) {
                    x = xt;
                }
            } else {
                while (i < prices.length && prices[i] < prices[min]) {
                    min = i;
                    i++;
                }
                max = i;
            }

        }

        return x;

    }
}
